package 链表;

/* https://leetcode-cn.com/problems/reverse-linked-list/ */
/* !!! 经典面试题 */

public class _206_反转链表 {

    public class ListNode {

        // value
        int val;
        // next
        ListNode next;
        // 无参的构造函数
        ListNode() {}
        // 有参的构造函数
        ListNode(int val) { this.val = val; }
        // 有参的构造函数
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    // 递归的方式
    public ListNode reverseList2(ListNode head) {

        // 如果这个链表是空的，或者这个链表只有一个node，那么返回他自己
        if (head == null || head.next == null){
            return head;
        }else {
        // 假如现在的head = [5,4,3,2,1],调用了reverseList2(head.next)后就变成了[5,1,2,3,4]（假设这个反转函数是写好的）
            ListNode new_head = reverseList2(head.next);
        // 此时head.next依旧指向的是4，我们要让4的next指向5，所以head.next.next = head(此时的head依旧是5)
            head.next.next = head;
        // 5的next现在要指向null
            head.next = null;
            return new_head;
        }
    }

    // 非递归的方式
    public ListNode reverseList(ListNode head) {

        // 先创建一个new_head让他为null作为最后一个node的next指向
        ListNode new_head = null;

        // 当head不为空的时候说明还没反转完
        while(head != null){

            // 临时变量tmp，相当于链表第二个node，用来被head.next指向
            ListNode tmp = head.next;
            // 链表头部分即反转后链表的尾部分的next，指向new_head(new_head = null)，即指向空
            head.next = new_head;
            // 让new_head的值变为原来的head的值
            new_head = head;
            // 让原来head的值变为原来tmp的值
            head = tmp;
        }
        // 返回这个新的链表
        return  new_head;

    }
}
